home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / New System Software Extensions / OpenDoc A6 / OpenDoc Parts Framework / OPF / OS / FWMemory / Sources / FWBestFH.cpp next >
Encoding:
Text File  |  1994-04-21  |  27.4 KB  |  959 lines  |  [TEXT/MPS ]
  1. //========================================================================================
  2. //
  3. //    File:                FWBestFH.cpp
  4. //    Release Version:    $ 1.0d1 $
  5. //
  6. //    Creation Date:        3/28/94
  7. //
  8. //    Copyright:    © 1993, 1994 by Apple Computer, Inc., all rights reserved.
  9. //
  10. //========================================================================================
  11.  
  12. #ifndef FWPLATME_H
  13. #include <FWPlatMe.h>
  14. #endif
  15.  
  16. #ifndef FWBESTFH_H
  17. #include <FWBestFH.h>
  18. #endif
  19.  
  20. #ifndef __MEMORY__
  21. #include <Memory.h>
  22. #endif
  23.  
  24. #ifndef __LIMITS__
  25. #include <limits.h>
  26. #endif
  27.  
  28. #ifndef __STRING__
  29. #include <string.h>
  30. #endif
  31.  
  32. #ifndef __STDIO__
  33. #include <stdio.h>
  34. #endif
  35.  
  36.  
  37. //========================================================================================
  38. // FW_CPrivBestFitBlock
  39. //========================================================================================
  40.  
  41. //----------------------------------------------------------------------------------------
  42. // FW_CPrivBestFitBlock::operator >
  43. //----------------------------------------------------------------------------------------
  44. #pragma segment HeapSeg
  45.  
  46. Boolean FW_CPrivBestFitBlock::operator>(const FW_CPrivBestFitBlock& blk) const
  47. {
  48.     if (GetSize() == blk.GetSize())
  49.         return this > &blk;
  50.     else
  51.         return GetSize() > blk.GetSize();
  52. }
  53.  
  54. //----------------------------------------------------------------------------------------
  55. // FW_CPrivBestFitBlock::operator <
  56. //----------------------------------------------------------------------------------------
  57. #pragma segment HeapSeg
  58.  
  59. Boolean FW_CPrivBestFitBlock::operator<(const FW_CPrivBestFitBlock& blk) const
  60. {
  61.     if (GetSize() == blk.GetSize())
  62.         return this < &blk;
  63.     else
  64.         return GetSize() < blk.GetSize();
  65. }
  66.  
  67. //----------------------------------------------------------------------------------------
  68. // FW_CPrivBestFitBlock::operator ==
  69. //----------------------------------------------------------------------------------------
  70. #pragma segment HeapSeg
  71.  
  72. Boolean FW_CPrivBestFitBlock::operator==(const FW_CPrivBestFitBlock& blk) const
  73. {
  74.     return GetSize() == blk.GetSize() && this == &blk;
  75. }
  76.  
  77. //----------------------------------------------------------------------------------------
  78. // FW_CPrivBestFitBlock::StuffAddressAtEnd
  79. //----------------------------------------------------------------------------------------
  80. #pragma segment HeapSeg
  81.  
  82. void FW_CPrivBestFitBlock::StuffAddressAtEnd()
  83. {
  84.     // coalescence possible in constant time.
  85.  
  86.     if (!this->GetBusy())
  87.     {
  88.         void** addr= (void**) ((FW_BytePtr) this + this->GetSize() - sizeof(FW_CPrivBestFitBlock *));
  89.         *addr = this;
  90.     }
  91. #ifdef FW_DEBUG
  92.     else
  93.         PLATFORM_DEBUGGER_STRING("FW_CPrivBestFitBlock::StuffAddressAtEnd: corrupt heap!");
  94. #endif
  95. }
  96.  
  97.  
  98. //========================================================================================
  99. // FW_CBestFitHeap
  100. //========================================================================================
  101.  
  102. //----------------------------------------------------------------------------------------
  103. // FW_CBestFitHeap::FW_CBestFitHeap
  104. //----------------------------------------------------------------------------------------
  105. #pragma segment HeapSeg
  106.  
  107. FW_CBestFitHeap::FW_CBestFitHeap(unsigned long sizeInitial,
  108.                                  unsigned long sizeIncrement) :
  109.     FW_CMemoryHeap(false, true, false)
  110. {
  111. #ifdef FW_DEBUG
  112.     CompilerCheck();
  113. #endif
  114.  
  115.     fSizeIncrement = sizeIncrement;
  116.     fSizeInitial = sizeInitial;
  117.     fSegments = NULL;
  118.  
  119. //    this->GrowHeap(fSizeInitial);    * MEB *
  120. }
  121.  
  122. //----------------------------------------------------------------------------------------
  123. // FW_CBestFitHeap::~FW_CBestFitHeap
  124. //----------------------------------------------------------------------------------------
  125. #pragma segment HeapSeg
  126.  
  127. FW_CBestFitHeap::~FW_CBestFitHeap()
  128. {
  129.     this->DeleteSegments();
  130. }
  131.  
  132. //----------------------------------------------------------------------------------------
  133. // FW_CBestFitHeap::IBestFitHeap    * MEB *
  134. //----------------------------------------------------------------------------------------
  135. #pragma segment HeapSeg
  136.  
  137. void FW_CBestFitHeap::IBestFitHeap()
  138. {
  139.     this->GrowHeap(fSizeInitial);
  140. }
  141.  
  142. //----------------------------------------------------------------------------------------
  143. // FW_CBestFitHeap::ExpandHeap    * MEB *
  144. //----------------------------------------------------------------------------------------
  145. #pragma segment HeapSeg
  146.  
  147. void FW_CBestFitHeap::ExpandHeap(unsigned long sizeInitial, unsigned long sizeIncrement)
  148. {
  149.     if (sizeInitial > fSizeInitial)
  150.         fSizeInitial = sizeInitial;
  151.     if (sizeIncrement > fSizeIncrement)
  152.         fSizeIncrement = sizeIncrement;
  153.     
  154.     if (sizeInitial > this->HeapSize())
  155.         this->GrowHeap(sizeInitial);
  156.     else
  157.         this->GrowHeap(sizeIncrement);
  158. }
  159.  
  160. //----------------------------------------------------------------------------------------
  161. // FW_CBestFitHeap::BytesFree
  162. //----------------------------------------------------------------------------------------
  163. #pragma segment HeapSeg
  164.  
  165. unsigned long FW_CBestFitHeap::BytesFree() const
  166. {
  167.     unsigned long bytesFree, numberOfNodes;
  168.  
  169.     fFreeTree.TreeInfo(bytesFree, numberOfNodes);
  170.     bytesFree -= numberOfNodes * FW_CPrivBestFitBlock::kBusyOverhead;
  171.  
  172.     return bytesFree;
  173. }
  174.  
  175. #ifdef FW_DEBUG
  176. //----------------------------------------------------------------------------------------
  177. // FW_CBestFitHeap::Check
  178. //----------------------------------------------------------------------------------------
  179. #pragma segment HeapSeg
  180.  
  181. void FW_CBestFitHeap::Check() const
  182. {
  183.     fFreeTree.CheckTree();
  184. }
  185. #endif
  186.  
  187. //----------------------------------------------------------------------------------------
  188. // FW_CBestFitHeap::DoAllocate
  189. //----------------------------------------------------------------------------------------
  190. #pragma segment HeapSeg
  191.  
  192. void* FW_CBestFitHeap::DoAllocate(FW_BlockSize size, FW_BlockSize& allocatedSize)
  193. {
  194.     FW_BlockSize blkSize = size + FW_CPrivBestFitBlock::kBusyOverhead;
  195.  
  196.     if (blkSize < FW_CPrivBestFitBlock::kMinBlockSize)
  197.         blkSize = FW_CPrivBestFitBlock::kMinBlockSize;
  198.  
  199.     // Make sure blkSize is even
  200.  
  201.     if (blkSize & 0x01)
  202.         blkSize++;
  203.  
  204. #ifdef FW_DEBUG
  205.     PLATFORM_ASSERT(blkSize <= BestFitBlock_kMaxBlockSize);
  206. #endif
  207.  
  208.     FW_CPrivBestFitBlock * blk = this->SearchFreeBlocks(blkSize);
  209.  
  210.     // Make an attempt to expand the heap
  211.  
  212.     if (blk == NULL && fSizeIncrement > 0)
  213.     {
  214.         this->GrowHeap(fSizeIncrement);
  215.         blk = this->SearchFreeBlocks(blkSize);
  216.     }
  217.  
  218.     allocatedSize = 0;
  219.     void* newPtr = NULL;
  220.  
  221.     if (blk != NULL)
  222.     {
  223.         // We found a block, so mark it busy and remove it from the free list.
  224.  
  225.         blk->SetBusy(true);
  226.         this->RemoveFromFreeBlocks(blk);
  227.  
  228.         if (blk->GetSize() - blkSize >= FW_CPrivBestFitBlock::kMinBlockSize)
  229.         {
  230.             // The block is big enough to split, so here we do the split.
  231.  
  232.             FW_CPrivBestFitBlock *newBlk
  233.                 = new((void *) ((FW_BytePtr) blk + blkSize))
  234.                     FW_CPrivBestFitBlock(false, true, blk->GetSize() - blkSize);
  235.             this->AddToFreeBlocks(newBlk);
  236.             blk->SetSize(blkSize);
  237.         }
  238.  
  239.         FW_CPrivBestFitBlock * nextBlk
  240.             = (FW_CPrivBestFitBlock *) ((FW_BytePtr) blk + blk->GetSize());
  241.         nextBlk->SetPrevBusy(true);
  242.  
  243.         newPtr = (void *) ((FW_BytePtr) blk + FW_CPrivBestFitBlock::kBusyOverhead);
  244.         allocatedSize = blk->GetSize() - FW_CPrivBestFitBlock::kBusyOverhead;
  245.     }
  246.  
  247.     return newPtr;
  248. }
  249.  
  250. //----------------------------------------------------------------------------------------
  251. // FW_CBestFitHeap::DoBlockSize
  252. //----------------------------------------------------------------------------------------
  253. #pragma segment HeapSeg
  254.  
  255. FW_BlockSize FW_CBestFitHeap::DoBlockSize(const void* block) const
  256. {
  257.     FW_CPrivBestFitBlock * blk
  258.         = (FW_CPrivBestFitBlock *) ((FW_BytePtr) block - FW_CPrivBestFitBlock::kBusyOverhead);
  259.  
  260. #ifdef FW_DEBUG
  261.     PLATFORM_ASSERT(blk->GetBusy());
  262. #endif
  263.     
  264.     return blk->GetSize() - FW_CPrivBestFitBlock::kBusyOverhead;
  265. }
  266.  
  267. //----------------------------------------------------------------------------------------
  268. // FW_CBestFitHeap::DoFree
  269. //----------------------------------------------------------------------------------------
  270. #pragma segment HeapSeg
  271.  
  272. void FW_CBestFitHeap::DoFree(void* ptr)
  273. {
  274.     FW_CPrivBestFitBlock *blk
  275.         = (FW_CPrivBestFitBlock *) ((FW_BytePtr) ptr - FW_CPrivBestFitBlock::kBusyOverhead);
  276.  
  277. #ifdef FW_DEBUG
  278.     PLATFORM_ASSERT(blk->GetBusy());
  279. #endif
  280.     
  281.     blk->SetBusy(false);
  282.     blk->StuffAddressAtEnd();
  283.  
  284.     FW_CPrivBestFitBlock *nextBlk
  285.         = (FW_CPrivBestFitBlock *) ((FW_BytePtr) blk + blk->GetSize());
  286.     nextBlk->SetPrevBusy(false);
  287.  
  288.     if (this->Coalesce(nextBlk))
  289.         this->RemoveFromFreeBlocks(nextBlk);
  290.  
  291.     FW_CPrivBestFitBlock * prevBlk = this->Coalesce(blk);
  292.     if (prevBlk)
  293.     {
  294.         this->RemoveFromFreeBlocks(prevBlk);
  295.         this->AddToFreeBlocks(prevBlk);
  296.     }
  297.     else
  298.         this->AddToFreeBlocks(blk);
  299. }
  300.  
  301. #ifdef FW_DEBUG
  302. //----------------------------------------------------------------------------------------
  303. // FW_CBestFitHeap::DoIsValidBlock
  304. //----------------------------------------------------------------------------------------
  305. #pragma segment HeapSeg
  306.  
  307. Boolean FW_CBestFitHeap::DoIsValidBlock(void* ptr) const
  308. {
  309.     FW_CPrivBestFitBlock *blk 
  310.         = (FW_CPrivBestFitBlock *) ((FW_BytePtr) ptr - FW_CPrivBestFitBlock::kBusyOverhead);
  311.  
  312.     FW_BlockSize blkSize = blk->GetSize();
  313.  
  314.     return (blkSize <= fSizeIncrement || blkSize <= fSizeInitial) && blk->GetBusy() && blk->GetMagicNumber() == (unsigned int)FW_CPrivBestFitBlock::kMagicNumber;
  315. }
  316. #endif
  317.  
  318. //----------------------------------------------------------------------------------------
  319. // FW_CBestFitHeap::DoReset
  320. //----------------------------------------------------------------------------------------
  321. #pragma segment HeapSeg
  322.  
  323. void FW_CBestFitHeap::DoReset()
  324. {
  325.     this->DeleteSegments();
  326.     fSegments = NULL;
  327.     fFreeTree = FW_CPrivFreeBlockTree();
  328.  
  329.     this->GrowHeap(fSizeInitial);
  330. }
  331.  
  332. //----------------------------------------------------------------------------------------
  333. // FW_CBestFitHeap::HeapSize
  334. //----------------------------------------------------------------------------------------
  335. #pragma segment HeapSeg
  336.  
  337. unsigned long FW_CBestFitHeap::HeapSize() const
  338. {
  339.     FW_CPrivBestFitSegment * segment = fSegments;
  340.     unsigned long heapSize = 0;
  341.  
  342.     while (segment != NULL)
  343.     {
  344.         heapSize += segment->fSegmentSize;
  345.         segment = segment->fNextSegment;
  346.     }
  347.  
  348.     return heapSize;
  349. }
  350.  
  351. #ifdef FW_DEBUG
  352. //----------------------------------------------------------------------------------------
  353. // FW_CBestFitHeap::IsMyBlock
  354. //----------------------------------------------------------------------------------------
  355. #pragma segment HeapSeg
  356.  
  357. Boolean FW_CBestFitHeap::IsMyBlock(void* blk) const
  358. {
  359.     Boolean myBlock = false;
  360.  
  361.     FW_CPrivBestFitSegment * segment = fSegments;
  362.     while (segment != NULL && myBlock == false)
  363.     {
  364.         myBlock = segment->AddressInSegment(blk);
  365.         segment = segment->fNextSegment;
  366.     }
  367.  
  368.     return myBlock;
  369. }
  370. #endif
  371.  
  372. #ifdef FW_DEBUG
  373. //----------------------------------------------------------------------------------------
  374. // FW_CBestFitHeap::Print
  375. //----------------------------------------------------------------------------------------
  376. #pragma segment HeapSeg
  377.  
  378. void FW_CBestFitHeap::Print(char* msg) const
  379. {
  380.     PLATFORM_PRINT_STRING("********** FW_CBestFitHeap **********\n");
  381.     fFreeTree.PrintTree();
  382.     PLATFORM_PRINT_STRING("\n");
  383. }
  384. #endif
  385.  
  386. //----------------------------------------------------------------------------------------
  387. // FW_CBestFitHeap::AddToFreeBlocks
  388. //----------------------------------------------------------------------------------------
  389. #pragma segment HeapSeg
  390.  
  391. void FW_CBestFitHeap::AddToFreeBlocks(FW_CPrivBestFitBlock* blk)
  392. {
  393.     fFreeTree.AddBlock(blk);
  394. }
  395.  
  396. //----------------------------------------------------------------------------------------
  397. // FW_CBestFitHeap::Coalesce: Coalesce blk with the previous block if both are free.
  398. //----------------------------------------------------------------------------------------
  399. #pragma segment HeapSeg
  400.  
  401. FW_CPrivBestFitBlock* FW_CBestFitHeap::Coalesce(FW_CPrivBestFitBlock* blk)
  402. {
  403.     FW_CPrivBestFitBlock * prevBlk = NULL;
  404.  
  405.     if (!blk->GetBusy() && !blk->GetPreviousBusy())
  406.     {
  407. #ifdef FW_DEBUG
  408.         if (blk->GetSize() < FW_CPrivBestFitBlock::kMinBlockSize)
  409.             PLATFORM_DEBUGGER_STRING("FW_CBestFitHeap::Coalesce: corrupt heap!");
  410. #endif
  411.             
  412.         prevBlk = *(FW_CPrivBestFitBlock **) ((FW_BytePtr) blk - sizeof(FW_BlockSize));
  413.         prevBlk->SetSize(prevBlk->GetSize() + blk->GetSize());
  414.         prevBlk->StuffAddressAtEnd();
  415.     }
  416.  
  417.     return prevBlk;
  418. }
  419.  
  420. //----------------------------------------------------------------------------------------
  421. // FW_CBestFitHeap::CreateNewSegment
  422. //----------------------------------------------------------------------------------------
  423. #pragma segment HeapSeg
  424.  
  425. void FW_CBestFitHeap::CreateNewSegment(unsigned long size)
  426. {
  427. #ifdef BUILD_WIN16
  428.     PLATFORM_ASSERT(size < 64L * 1024L);
  429. #endif
  430.  
  431.     if (size & 0x01)
  432.         size++;
  433.  
  434.     FW_CPrivBestFitSegment * segment
  435.         = (FW_CPrivBestFitSegment *)this->AllocateRawMemory((FW_BlockSize) size);
  436.  
  437.     // The actual usable space is offset by the size of the fields
  438.     // of a FW_CPrivBestFitSegment.
  439.  
  440.     segment->fSegmentSpace 
  441.         = (void *) ((FW_BytePtr) segment + FW_CPrivBestFitSegment::kSegmentPrefixSize);
  442.     segment->fSegmentSize = size - FW_CPrivBestFitSegment::kSegmentPrefixSize;
  443.  
  444.     // Add the segment to the list of segments in this heap.
  445.  
  446.     segment->fNextSegment = fSegments;
  447.     fSegments = segment;
  448.  
  449.     // Suffix the segment with a busy block of zero length so that the last free
  450.     // block is not coalesced with a block past the fEnd of the segment.
  451.  
  452.     void * endOfSegment 
  453.         = (void *) ((FW_BytePtr) segment->fSegmentSpace + segment->fSegmentSize);
  454.     FW_CPrivBestFitBlock *blk
  455.         = new((void *) ((FW_BytePtr) endOfSegment - sizeof(FW_CPrivBestFitBlock)))
  456.             FW_CPrivBestFitBlock(true, false, 0);
  457.  
  458.     // Create one free block out of this entire segment and Add it to the
  459.     // free block list.
  460.  
  461.     blk = new(segment->fSegmentSpace)FW_CPrivBestFitBlock(false, true, segment->fSegmentSize - sizeof(FW_CPrivBestFitBlock));
  462.  
  463.     this->AddToFreeBlocks(blk);
  464. }
  465.  
  466. //----------------------------------------------------------------------------------------
  467. // FW_CBestFitHeap::DeleteSegments
  468. //----------------------------------------------------------------------------------------
  469. #pragma segment HeapSeg
  470.  
  471. void FW_CBestFitHeap::DeleteSegments()
  472. {
  473.     FW_CPrivBestFitSegment * segment = fSegments;
  474.     while (segment != NULL)
  475.     {
  476.         FW_CPrivBestFitSegment * nextSegment = segment->fNextSegment;
  477.         this->FreeRawMemory(segment);
  478.         segment = nextSegment;
  479.     }
  480. }
  481.  
  482. //----------------------------------------------------------------------------------------
  483. // FW_CBestFitHeap::GrowHeap
  484. //----------------------------------------------------------------------------------------
  485. #pragma segment HeapSeg
  486.  
  487. void FW_CBestFitHeap::GrowHeap(unsigned long sizeIncrement)
  488. {
  489. #ifdef BUILD_WIN16
  490.     // To avoid crossing 64K boundries on pointer arithmatic, the size of each segment
  491.     // must be limited to 64K. So a single grow request may result in more than one
  492.     // segment being allocated.
  493.     
  494.     const unsigned long kSegmentSizeLimit = 1024L * 62L;     // Allow for 2K overhead
  495.     
  496.     while (sizeIncrement > 0)
  497.     {
  498.         unsigned long segmentSize = sizeIncrement;
  499.         if (segmentSize > kSegmentSizeLimit)
  500.             segmentSize = kSegmentSizeLimit;
  501.         this->CreateNewSegment(segmentSize);
  502.         sizeIncrement -= segmentSize;
  503.     }
  504. #else
  505.     this->CreateNewSegment(sizeIncrement);
  506. #endif
  507. }
  508.  
  509. //----------------------------------------------------------------------------------------
  510. // FW_CBestFitHeap::RemoveFromFreeBlocks
  511. //----------------------------------------------------------------------------------------
  512. #pragma segment HeapSeg
  513.  
  514. void FW_CBestFitHeap::RemoveFromFreeBlocks(FW_CPrivBestFitBlock* blk)
  515. {
  516.     fFreeTree.RemoveBlock(blk);
  517. }
  518.  
  519. //----------------------------------------------------------------------------------------
  520. // FW_CBestFitHeap::SearchFreeBlocks
  521. //----------------------------------------------------------------------------------------
  522. #pragma segment HeapSeg
  523.  
  524. FW_CPrivBestFitBlock* FW_CBestFitHeap::SearchFreeBlocks(FW_BlockSize size)
  525. {
  526.     //all blocks are of even length, so round up to fNext even number
  527.  
  528.     if (size & 1)
  529.         size++;
  530.  
  531.     return fFreeTree.SearchForBlock(size, NULL, NULL);
  532. }
  533.  
  534. #ifdef FW_DEBUG
  535. //----------------------------------------------------------------------------------------
  536. // FW_CBestFitHeap::CompilerCheck
  537. //----------------------------------------------------------------------------------------
  538. #pragma segment HeapSeg
  539.  
  540. void FW_CBestFitHeap::CompilerCheck()
  541. {
  542.     FW_CMemoryHeap::CompilerCheck();
  543.     
  544.     char buffer[sizeof(FW_CPrivBestFitBlock) + sizeof(void *)];
  545.     FW_CPrivBestFitBlock &block = *((FW_CPrivBestFitBlock *) buffer);
  546.         
  547.     // Check to make sure the bit field setters and getters work.
  548.     
  549.     block.SetBlockType(3);
  550.     block.SetBusy(true);
  551.     block.SetPrevBusy(false);
  552. #ifndef BUILD_WIN16
  553.     block.SetSize(100201);
  554. #endif
  555.     block.SetMagicNumber(3);
  556.  
  557.     PLATFORM_ASSERT(block.GetBlockType() == 3);
  558.     PLATFORM_ASSERT(block.GetBusy() == true);
  559.     PLATFORM_ASSERT(block.GetPreviousBusy() == false);
  560. #ifndef BUILD_WIN16
  561.     PLATFORM_ASSERT(block.GetSize() == 100201);
  562. #endif
  563.     PLATFORM_ASSERT(block.GetMagicNumber() == 3);
  564.     
  565.     block.SetBlockType(2);
  566.     block.SetBusy(false);
  567.     block.SetPrevBusy(true);
  568.     block.SetSize(150);
  569.     block.SetMagicNumber(2);
  570.  
  571.     PLATFORM_ASSERT(block.GetBlockType() == 2);
  572.     PLATFORM_ASSERT(block.GetBusy() == false);
  573.     PLATFORM_ASSERT(block.GetPreviousBusy() == true);
  574.     PLATFORM_ASSERT(block.GetSize() == 150);
  575.     PLATFORM_ASSERT(block.GetMagicNumber() == 2);
  576. }
  577. #endif
  578.  
  579.  
  580. //========================================================================================
  581. // CLASS FW_CPrivFreeBlockTree
  582. //========================================================================================
  583.  
  584. //----------------------------------------------------------------------------------------
  585. // FW_CPrivFreeBlockTree::FW_CPrivFreeBlockTree
  586. //----------------------------------------------------------------------------------------
  587. #pragma segment HeapSeg
  588.  
  589. FW_CPrivFreeBlockTree::FW_CPrivFreeBlockTree() :
  590.     fRoot(true, true, 0)
  591. {
  592.     fRoot.SetRight(NULL);
  593.     fRoot.SetLeft(NULL);
  594. }
  595.  
  596. //----------------------------------------------------------------------------------------
  597. // FW_CPrivFreeBlockTree::FW_CPrivFreeBlockTree
  598. //----------------------------------------------------------------------------------------
  599. #pragma segment HeapSeg
  600.  
  601. FW_CPrivFreeBlockTree::FW_CPrivFreeBlockTree(const FW_CPrivFreeBlockTree& blk) :
  602.     fRoot(blk.fRoot)
  603. {
  604. }
  605.  
  606. //----------------------------------------------------------------------------------------
  607. // FW_CPrivFreeBlockTree::operator=
  608. //----------------------------------------------------------------------------------------
  609. #pragma segment HeapSeg
  610.  
  611. FW_CPrivFreeBlockTree& FW_CPrivFreeBlockTree::operator=(const FW_CPrivFreeBlockTree& blk)
  612. {
  613.     fRoot = blk.fRoot;
  614.     return (*this);
  615. }
  616.  
  617. //----------------------------------------------------------------------------------------
  618. // FW_CPrivFreeBlockTree::AddBlock
  619. //----------------------------------------------------------------------------------------
  620. #pragma segment HeapSeg
  621.  
  622. void FW_CPrivFreeBlockTree::AddBlock(FW_CPrivBestFitBlock* blk)
  623. {    
  624. #ifdef FW_DEBUG
  625.     this->CheckTree();
  626.  
  627. #ifdef FW_INTENSE_DEBUG
  628.     PLATFORM_PRINT_STRING("FW_CPrivFreeBlockTree::AddBlock Entry-------------------------------------\n");
  629.     this->PrintTree();
  630. #endif
  631. #endif
  632.  
  633.     FW_CPrivBestFitBlock * parent;
  634.  
  635.     this->SearchForBlock(blk->GetSize(), blk, &parent);
  636.  
  637.     blk->SetRight(NULL);
  638.     blk->SetLeft(NULL);
  639.     blk->SetParent(parent);
  640.  
  641.     if (*blk > *parent)
  642.         parent->SetRight(blk);
  643.     else
  644.         parent->SetLeft(blk);
  645.  
  646. #ifdef FW_DEBUG
  647.     this->CheckTree();
  648.  
  649. #ifdef FW_INTENSE_DEBUG
  650.     PLATFORM_PRINT_STRING("FW_CPrivFreeBlockTree::AddBlock Exit\n");
  651.     this->PrintTree();
  652.     PLATFORM_PRINT_STRING("\n");
  653. #endif
  654. #endif
  655. }
  656.  
  657. #ifdef FW_DEBUG
  658. //----------------------------------------------------------------------------------------
  659. // FW_CPrivFreeBlockTree::CheckTree
  660. //----------------------------------------------------------------------------------------
  661. #pragma segment HeapSeg
  662.  
  663. void FW_CPrivFreeBlockTree::CheckTree() const
  664. {
  665.     this->CheckTreeHelper(&((FW_CPrivFreeBlockTree *)this)->fRoot);
  666. }
  667. #endif
  668.  
  669. #ifdef FW_DEBUG
  670. //----------------------------------------------------------------------------------------
  671. // FW_CPrivFreeBlockTree::PrintTree
  672. //----------------------------------------------------------------------------------------
  673. #pragma segment HeapSeg
  674.  
  675. void FW_CPrivFreeBlockTree::PrintTree() const
  676. {
  677.     this->PrintTreeHelper(&((FW_CPrivFreeBlockTree *)this)->fRoot);
  678. }
  679. #endif
  680.  
  681. //----------------------------------------------------------------------------------------
  682. // FW_CPrivFreeBlockTree::RemoveBlock
  683. //----------------------------------------------------------------------------------------
  684. #pragma segment HeapSeg
  685.  
  686. void FW_CPrivFreeBlockTree::RemoveBlock(FW_CPrivBestFitBlock* blk)
  687. {
  688. #ifdef FW_DEBUG
  689.     this->CheckTree();
  690.  
  691. #ifdef FW_INTENSE_DEBUG
  692.     PLATFORM_PRINT_STRING("FW_CPrivFreeBlockTree::RemoveBlock Entry----------------------------------\n");
  693.     this->PrintTree();
  694. #endif
  695. #endif
  696.  
  697.     FW_CPrivBestFitBlock * spliceOutBlk;
  698.  
  699.     // Decide which block to splice out of the tree. Either the block being
  700.     // removed, or its successor block in the tree.
  701.  
  702.     if (blk->GetLeft() == NULL || blk->GetRight() == NULL)
  703.         spliceOutBlk = blk;
  704.     else
  705.         spliceOutBlk = this->GetSuccessorBlk(blk);
  706.  
  707.     // Splice the node out of the tree
  708.  
  709.     FW_CPrivBestFitBlock * tmp;
  710.     FW_CPrivBestFitBlock * parent = spliceOutBlk->GetParent();
  711.     if (spliceOutBlk->GetLeft())
  712.         tmp = spliceOutBlk->GetLeft();
  713.     else
  714.         tmp = spliceOutBlk->GetRight();
  715.     if (tmp)
  716.         tmp->SetParent(parent);
  717.     if (spliceOutBlk == parent->GetLeft())
  718.         parent->SetLeft(tmp);
  719.     else
  720.         parent->SetRight(tmp);
  721.  
  722.     // If we spliced out the successor to blk above then we need to patch the successor
  723.     // back in, in Place of blk.
  724.  
  725.     if (spliceOutBlk != blk)
  726.     {
  727.         FW_CPrivBestFitBlock * parent = blk->GetParent();
  728.  
  729.         // Fix up the parent's child pointer.
  730.  
  731.         if (parent->GetLeft() == blk)
  732.             parent->SetLeft(spliceOutBlk);
  733.         else
  734.             parent->SetRight(spliceOutBlk);
  735.  
  736.         // Fix up the splice in block's pointers.
  737.  
  738.         spliceOutBlk->SetParent(parent);
  739.         spliceOutBlk->SetLeft(blk->GetLeft());
  740.         spliceOutBlk->SetRight(blk->GetRight());
  741.  
  742.         // Fix up the children of the splice in block's parent pointers.
  743.  
  744.         if (spliceOutBlk->GetLeft())
  745.             (spliceOutBlk->GetLeft())->SetParent(spliceOutBlk);
  746.         if (spliceOutBlk->GetRight())
  747.             (spliceOutBlk->GetRight())->SetParent(spliceOutBlk);
  748.     }
  749.  
  750. #ifdef FW_DEBUG
  751.     this->CheckTree();
  752.  
  753. #ifdef FW_INTENSE_DEBUG
  754.     PLATFORM_PRINT_STRING("FW_CPrivFreeBlockTree::RemoveBlock Exit\n");
  755.     this->PrintTree();
  756.     PLATFORM_PRINT_STRING("\n");
  757. #endif
  758. #endif
  759. }
  760.  
  761. //----------------------------------------------------------------------------------------
  762. // FW_CPrivFreeBlockTree::SearchForBlock
  763. //----------------------------------------------------------------------------------------
  764. #pragma segment HeapSeg
  765.  
  766. FW_CPrivBestFitBlock* FW_CPrivFreeBlockTree::SearchForBlock(FW_BlockSize size,
  767.                                             void* blk,
  768.                                             FW_CPrivBestFitBlock** insertLeaf)
  769. {
  770. #ifdef FW_DEBUG
  771.     this->CheckTree();
  772.  
  773. #ifdef FW_INTENSE_DEBUG
  774.     char str[80];
  775.     sprintf(str, "FW_CPrivFreeBlockTree::SearchForBlock(%d)---------------------------------\n", size);
  776.     PLATFORM_PRINT_STRING(str);
  777.     this->PrintTree();
  778. #endif
  779. #endif
  780.  
  781.     long minDiff = LONG_MAX;
  782.     FW_CPrivBestFitBlock * minDiffBlock = NULL;
  783.     FW_CPrivBestFitBlock * currentBlock = &fRoot;
  784.     do
  785.     {
  786.         long diff = currentBlock->GetSize() - size;
  787.         if (diff >= 0 && diff < minDiff)
  788.         {
  789.             minDiffBlock = currentBlock;
  790.             minDiff = diff;
  791.         }
  792.  
  793.         if (insertLeaf)
  794.             *insertLeaf = currentBlock;
  795.  
  796.         // Determine which branch of the tree to continue down. Since duplicate keys are
  797.         // difficult to deal with in binary trees, we use the address of blocks to break
  798.         // ties, in the case of two blocks whose size are equal.
  799.  
  800.         if (size < currentBlock->GetSize())
  801.             currentBlock = currentBlock->GetLeft();
  802.         else if (size > currentBlock->GetSize())
  803.             currentBlock = currentBlock->GetRight();
  804.         else if (blk)
  805.         {
  806.             if (blk <= currentBlock)
  807.                 currentBlock = currentBlock->GetLeft();
  808.             else
  809.                 currentBlock = currentBlock->GetRight();
  810.         }
  811.         else
  812.             currentBlock = currentBlock->GetLeft();
  813.  
  814.     } while (currentBlock != NULL);
  815.  
  816.     return minDiffBlock;
  817. }
  818.  
  819. //----------------------------------------------------------------------------------------
  820. // FW_CPrivFreeBlockTree::TreeInfo
  821. //----------------------------------------------------------------------------------------
  822. #pragma segment HeapSeg
  823.  
  824. void FW_CPrivFreeBlockTree::TreeInfo(unsigned long& bytesFree,
  825.                              unsigned long& numberOfNodes) const
  826. {
  827.     bytesFree = numberOfNodes = 0;
  828.     this->TreeInfoHelper(&((FW_CPrivFreeBlockTree *)this)->fRoot, bytesFree, numberOfNodes);
  829.  
  830.     // Subtract one from the number of nodes to account for the header node which
  831.     // is always empty.
  832.  
  833.     numberOfNodes--;
  834. }
  835.  
  836. #ifdef FW_DEBUG
  837. //----------------------------------------------------------------------------------------
  838. // FW_CPrivFreeBlockTree::CheckTreeHelper
  839. //----------------------------------------------------------------------------------------
  840. #pragma segment HeapSeg
  841.  
  842. void FW_CPrivFreeBlockTree::CheckTreeHelper(FW_CPrivBestFitBlock* blk) const
  843. {
  844.     if (blk == NULL)
  845.         return;
  846.  
  847.     this->CheckTreeHelper(blk->GetLeft());
  848.  
  849.     FW_CPrivBestFitBlock * parent = blk->GetParent();
  850.     if (parent != NULL)
  851.     {
  852.         if (parent->GetRight() == blk)
  853.         {
  854.             if (*blk < *parent)
  855.             {
  856.                 this->PrintTree();
  857.                 PLATFORM_DEBUGGER_STRING("FW_CPrivFreeBlockTree::CheckTreeHelper"
  858.                                              "Corrupt free list tree: "
  859.                                              "right child less than parent.");
  860.             }
  861.         }
  862.         else if (parent->GetLeft() == blk)
  863.         {
  864.             if (*blk > *parent)
  865.             {
  866.                 PLATFORM_DEBUGGER_STRING("FW_CPrivFreeBlockTree::CheckTreeHelper"
  867.                                              "Corrupt free list tree: "
  868.                                              "left child greater than parent.");
  869.             }
  870.         }
  871.         else
  872.         {
  873.                 PLATFORM_DEBUGGER_STRING("FW_CPrivFreeBlockTree::CheckTreeHelper"
  874.                                              "Corrupt free list tree: "
  875.                                              "I am not my parent's child.");
  876.         }
  877.     }
  878.  
  879.     // AMB_TODO: Recursing down the right side of the tree trashes the tree. This is
  880.     //             very strange, and as of yet I don't understand what the problem is. I
  881.     //             had suspected stack over-run.
  882.     //this->CheckTreeHelper(blk->GetRight());
  883. }
  884. #endif
  885.  
  886. //----------------------------------------------------------------------------------------
  887. // FW_CPrivFreeBlockTree::GetSuccessorBlk
  888. //----------------------------------------------------------------------------------------
  889. #pragma segment HeapSeg
  890.  
  891. FW_CPrivBestFitBlock* FW_CPrivFreeBlockTree::GetSuccessorBlk(FW_CPrivBestFitBlock* blk)
  892. {
  893.     if (blk->GetRight())
  894.     {
  895.         FW_CPrivBestFitBlock * current = blk->GetRight();
  896.         while (current->GetLeft())
  897.             current = current->GetLeft();
  898.         return current;
  899.     }
  900.     else
  901.     {
  902.         FW_CPrivBestFitBlock * parent = blk->GetParent();
  903.         FW_CPrivBestFitBlock * current = NULL;
  904.         while (parent != NULL && current == parent->GetRight())
  905.         {
  906.             current = parent;
  907.             parent = parent->GetParent();
  908.         }
  909.         return parent;
  910.     }
  911. }
  912.  
  913. #ifdef FW_DEBUG
  914. //----------------------------------------------------------------------------------------
  915. // FW_CPrivFreeBlockTree::PrintTreeHelper
  916. //----------------------------------------------------------------------------------------
  917. #pragma segment HeapSeg
  918.  
  919. void FW_CPrivFreeBlockTree::PrintTreeHelper(FW_CPrivBestFitBlock* blk,
  920.                                         int level) const
  921. {
  922.     for (int i = 0; i < level; i++)
  923.         PLATFORM_PRINT_STRING("\t");
  924.  
  925.     if (blk == NULL)
  926.     {
  927.         PLATFORM_PRINT_STRING("NULL\n");
  928.         return;
  929.     }
  930.  
  931.     char str[80];
  932.     //sprintf(str, "Block=%lx fSize=%ld\n", blk, blk->GetSize());
  933.     PLATFORM_PRINT_STRING(str);
  934.  
  935.     this->PrintTreeHelper(blk->GetLeft(), level + 1);
  936.     this->PrintTreeHelper(blk->GetRight(), level + 1);
  937. }
  938. #endif
  939.  
  940. //----------------------------------------------------------------------------------------
  941. // FW_CPrivFreeBlockTree::TreeInfoHelper
  942. //----------------------------------------------------------------------------------------
  943. #pragma segment HeapSeg
  944.  
  945. void FW_CPrivFreeBlockTree::TreeInfoHelper(FW_CPrivBestFitBlock* blk,
  946.                                        unsigned long& bytesFree,
  947.                                        unsigned long& numberOfNodes) const
  948. {
  949.     if (blk == NULL)
  950.         return;
  951.  
  952.     this->TreeInfoHelper(blk->GetLeft(), bytesFree, numberOfNodes);
  953.  
  954.     numberOfNodes++;
  955.     bytesFree += blk->GetSize();
  956.  
  957.     this->TreeInfoHelper(blk->GetRight(), bytesFree, numberOfNodes);
  958. }
  959.